#include <iostream>
#include <vector>
#include <sys/time.h>
#include <cstdlib>
#include "BinarySearchTree.h"

#define TESTNUM 30
#define N 10
#define CALTIME (end.tv_sec - start.tv_sec) * 1000 + (end.tv_usec - start.tv_usec) / 1000

using namespace::std;

/**
* @brief To print out the elements of vector b.
* 
* @param b
*/
template <typename T>
void printout( vector<T> & b)
{
    int num = b.size();
    for (int i = 0; i < num; i++)
        cout << b[i] << " ";
    cout << endl;
}

/**
* @brief To calculate the average number of the array.
* 
* @param num, size
*/
int average(const int* num, const int size)
{
    int ave = 0;
    for (int i = 0; i < size; i++)
    {
    ave += num[i];
    }
    ave /= size;
    return ave;
}

/**
* @brief To test the function and compare the effeciency of two sort function.
* 
*/
int main()
{
    // To test whether these sort functions are reliable.
    BinarySearchTree<int> a;
    vector<int> b;

    cout << "Test whether the BinarySearchTree works for 30 elements." << endl;
    for (int i = 0; i < TESTNUM; i++)
        b.push_back( rand() % 100 );
    cout << "The initial vector is: ";
    printout(b);

    vector<int> c(b);
    a.BST_sort(c);
    cout << endl;
    a.recover(c);
    cout << "After BST_sort, the vector is: ";
    printout(c);

    c = b;
    a.Randomized_BST_sort(c);
    a.recover(c);
    cout << "After Randomized_BST_sort, the vector is: ";
    printout(c);

    // To test the efficiency whether dicord or not.
    cout << "Efficiency fo the two types of sorts." << endl;
    BinarySearchTree<int> A;
    vector<int> X[N], Y[N], Z[N], H[N];
    int allnum;
    struct timeval start, end;
    int ranBST, ranRAD, incBST, incRAD, desBST, desRAD;
    int ran1[N], ran2[N], inc1[N], inc2[N], des1[N], des2[N];

    // Choose different value of allnum to test the efficiency.
    while(1)
    {
        cin >> allnum;
        if(allnum == -1)
            break;
        cout << "Total number of testing element is " << allnum << endl;
        for (int k = 0; k < N; k++)
        {
            // Test for random number
            for (int i = 0; i < allnum; i++)
                X[k].push_back( rand() % 200000);
            H[k].clear();
            H[k] = X[k];
            A.makeEmpty();
            gettimeofday( &start, NULL);
            A.BST_sort( H[k] );
            gettimeofday( &end, NULL);
            ran1[k] = CALTIME;

            A.makeEmpty();
            gettimeofday( &start, NULL);
            A.Randomized_BST_sort( H[k] );
            gettimeofday( &end, NULL);
            ran2[k] = CALTIME;

            // Test for increse in order
            Y[k].clear();
            for (int i = 0; i < allnum; i++)
                Y[k].push_back( i );
            A.makeEmpty();
            gettimeofday( &start, NULL);
            A.BST_sort( Y[k] );
            gettimeofday( &end, NULL);
            inc1[k] = CALTIME;

            A.makeEmpty();
            gettimeofday( &start, NULL);
            A.Randomized_BST_sort( Y[k] );
            gettimeofday( &end, NULL);
            inc2[k] = CALTIME;

            // Test for decrese in order
            Z[k].clear();
            for (int i = 0; i < allnum; i++)
                Z[k].push_back( allnum - i );
            A.makeEmpty();
            gettimeofday( &start, NULL);
            A.BST_sort( Z[k] );
            gettimeofday( &end, NULL);
            des1[k] = CALTIME;

            A.makeEmpty();
            gettimeofday( &start, NULL);
            A.Randomized_BST_sort( Z[k] );
            gettimeofday( &end, NULL);
            des2[k] = CALTIME;
        }

        // To get the average time.
        ranBST = average( ran1, N );
        ranRAD = average( ran2, N );
        incBST = average( inc1, N );
        incRAD = average( inc2, N );
        desBST = average( des1, N );
        desRAD = average( des2, N );

        cout << "The average time to BST_sort for random elements is " << ranBST << " ms" << endl;
        cout << "The average time to Randomized_BST_sort for random elements is " << ranRAD << " ms" << endl;
        cout << "The average time to BST_sort for increase elements is " << incBST << " ms" << endl;
        cout << "The average time to Randomized_BST_sort for increase elements is " << incRAD << " ms" << endl;
        cout << "The average time to BST_sort for decrease elements is " << desBST << " ms" << endl;
        cout << "The average time to Randomized_BST_sort for decrease elements is " << desRAD << " ms" << endl;
    }
    

    return 0;
}